λ¬Έμ
π Logic
private void canCheck(int[] friends) {
for (int i = 0; i < weak.length; i++) {
int start = i;
boolean canCheck = true;
for (int idx = 0; idx < friends.length; idx++) {
for (int j = i; j < i + weak.length; j++) {
// λ μ§μ κ° κ±°λ¦¬κ° friendsλ‘ λ½ν μΉκ΅¬κ° μ κ² κ°λ₯ν κ±°λ¦¬λ³΄λ€ ν° κ²½μ°λ μ κ² λΆκ°λ₯
// λ°λΌμ νμ¬ μ§μ μ μμμ μΌλ‘ μ§μ
if (unrolledWeak[j] - unrolledWeak[start] > friends[idx]) {
start = j;
idx++;
// νμ¬ μ§μ μ μ κ²ν μ μλλ°, λ μ κ²ν μΉκ΅¬κ° μλ€λ©΄, μ’
λ£
if (idx == friends.length) {
canCheck = false;
break;
}
}
}
// μ κ² μλ£λΌλ©΄, λ μ΄μ μ κ²ν νμκ° μλ€. λ°λΌμ flagλ₯Ό true μ§μ
if (canCheck) {
answer = idx + 1;
isFinish = true;
return;
}
}
}
}
- λ§λ€μ΄μ§ μ κ² μΈμμ μ΄μ©ν΄ μ κ²μ΄ κ°λ₯νμ§ νμΈνλ€.
- μ·¨μ½ μ§μ κ° κ±°λ¦¬λ₯Ό νμνλ©΄μ, λͺ¨λ μ κ²μ΄ κ°λ₯νλ€λ©΄
answerλidx + 1λ‘ μ λ°μ΄νΈλκ³ , μ’ λ£λ₯Ό μν΄isFinishλ₯Ό μ λ°μ΄νΈν΄ μμ΄ λ§λλ κ²μ μ’ λ£νλ€. - μ κ² μΈμμ λͺ¨λ λμν΄λ μ κ²μ΄ λΆκ°λ₯νλ€λ©΄, λμ΄μ νμμ μ’ λ£νκ³ , λ€μ μ κ² μΈμ μμ΄μ λ§λ λ€.
π CODE
μ½λ 보기/μ κΈ°π«
class Solution {
static int[] unrolledWeak;
static boolean isFinish;
static int[] weak;
static int[] dist;
static int answer = Integer.MAX_VALUE;
public int solution(int n, int[] weak, int[] dist) {
this.weak = weak;
this.dist = dist;
this.isFinish = false;
int distLen = dist.length;
unrollWeak(n, weak);
// iκ°μ μμ΄ λ§λ€κΈ°
for (int i = 1; i <= distLen; i++)
makeDistPerm(0, i, new boolean[distLen], new int[i]);
return answer == Integer.MAX_VALUE ? -1 : answer;
}
private void makeDistPerm(int depth, int count, boolean[] visited, int[] friends) {
if (isFinish) return;
if (depth == count) {
canCheck(friends);
return;
}
for (int i = 0; i < dist.length; i++) {
if (!visited[i]) {
friends[depth] = dist[i];
visited[i] = true;
makeDistPerm(depth + 1, count, visited, friends);
visited[i] = false;
}
}
}
private void canCheck(int[] friends) {
for (int i = 0; i < weak.length; i++) {
int start = i;
boolean canCheck = true;
for (int idx = 0; idx < friends.length; idx++) {
for (int j = i; j < i + weak.length; j++) {
// λ μ§μ κ° κ±°λ¦¬κ° friendsλ‘ λ½ν μΉκ΅¬κ° μ κ² κ°λ₯ν κ±°λ¦¬λ³΄λ€ ν° κ²½μ°λ μ κ² λΆκ°λ₯
// λ°λΌμ νμ¬ μ§μ μ μμμ μΌλ‘ μ§μ
if (unrolledWeak[j] - unrolledWeak[start] > friends[idx]) {
start = j;
idx++;
// νμ¬ μ§μ μ μ κ²ν μ μλλ°, λ μ κ²ν μΉκ΅¬κ° μλ€λ©΄, μ’
λ£
if (idx == friends.length) {
canCheck = false;
break;
}
}
}
// μ κ² μλ£λΌλ©΄, λ μ΄μ μ κ²ν νμκ° μλ€. λ°λΌμ flagλ₯Ό true μ§μ
if (canCheck) {
answer = idx + 1;
isFinish = true;
return;
}
}
}
}
// weakλ₯Ό 1μ°¨μμΌλ‘ νΌμΉ¨
private void unrollWeak(int n, int[] weak) {
int len = weak.length;
unrolledWeak = new int[len * 2 - 1];
System.arraycopy(weak, 0, unrolledWeak, 0, len);
for (int i = 0; i < len - 1; i++)
unrolledWeak[i + len] = weak[i] + n;
}
}
βοΈ Review
-
μμ΄μ μ¬μ©ν΄μ 1, 2, ... nλͺ μΌλ‘ κ°λ₯νμ§ νμΈν΄λ³΄λ λ°©μμΈ κ²μ μ½κ² μμλ€!
- νμ§λ§ μ£Όμ΄μ§ μΈμμΌλ‘ μΈλ²½ μ κ²μ΄ κ°λ₯νμ§ νμΈνλ λ‘μ§ κ΅¬νμμ μ’ λ§νλ€...
- ꡬν μ°μ΅μ λ§μ΄ ν΄μΌκ² λ€.